import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution76 {
    public String minWindow(String s, String t) {
        int[] bounds = new int[3];
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> pattern = new HashMap<>();
        for (int i = 0; i < t.length(); i++)
            pattern.put(t.charAt(i), pattern.getOrDefault(t.charAt(i), 0) + 1);
        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            boolean isTargetChar = pattern.containsKey(s.charAt(windowEnd));
            if (isTargetChar)
                window.put(s.charAt(windowEnd), window.getOrDefault(s.charAt(windowEnd), 0) + 1);
            //core part, shrink the window
            //todo 判定window已经满足条件的方法可以优化，无需检查完整map，可以迭代记载已经满足了的pattern中的字母个数
            while (windowEnd - windowStart + 1 >= t.length() && exceedsPatternLimit(window, pattern)) {
                updateMinsub(bounds, windowStart, windowEnd);
                if (window.containsKey(s.charAt(windowStart)))
                    window.put(s.charAt(windowStart), window.get(s.charAt(windowStart)) - 1);
                windowStart++;
            }

        }
        String minSub = "";
        if (bounds[0] == 0)
            return "";
        return s.substring(bounds[1], bounds[2] + 1);
    }


    public boolean exceedsPatternLimit(HashMap<Character, Integer> window, HashMap<Character, Integer> pattern) {
        boolean possibleExceeds = false;
        for (Map.Entry e : pattern.entrySet()) {
            if (window.getOrDefault(e.getKey(), 0) < (Integer) e.getValue())
                return false;
            else if (window.getOrDefault(e.getKey(), 0) >= (Integer) e.getValue())
                possibleExceeds = true;
        }
        return possibleExceeds;
    }

    public void updateMinsub(int[] bounds, int windowStart, int windowEnd) {
        if (bounds[0] == 0) {
            bounds[1] = windowStart;
            bounds[2] = windowEnd;
            bounds[0] = 1;
        } else if (windowEnd - windowStart + 1 < bounds[2] - bounds[1] + 1) {
            bounds[1] = windowStart;
            bounds[2] = windowEnd;
        }
    }

    public boolean reachPatternLimit(HashMap<Character, Integer> window, HashMap<Character, Integer> pattern) {
        //todo needs to be redifined
        for (Map.Entry e : pattern.entrySet()) {
            if (window.getOrDefault(e.getKey(), 0) < (Integer) e.getValue())
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution76().minWindow("a", "a"));
//        HashMap<String,Integer> map1 = new HashMap<>();
//        HashMap<String, Integer> map2 = new HashMap<>();
//        map1.put("A",130);
//        map2.put("A",130);
//        System.out.println(map1.get("A") == map2.get("A"));
    }
}
